/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-07-29
 * Time: 20:16
 */


  class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

public class Test {
      public ListNode createList() {
          ListNode A = new ListNode(1);
          ListNode B = new ListNode(1);
          ListNode C = new ListNode(1);
          ListNode D = new ListNode(1);
          ListNode E = new ListNode(1);
          ListNode F = new ListNode(1);
          ListNode G = new ListNode(1);
          A.next = B;
          B.next = C;
          C.next = D;
          D.next = E;
          E.next = F;
          F.next = G;

          return A;
      }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode phead = new ListNode(-1);
        ListNode cur = phead;
        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            }else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if(list1 != null) {
            cur.next = list1;
        }
        if(list2 != null) {
            cur.next = list2;
        }

        return phead.next;
    }

    public ListNode deleteDuplication(ListNode pHead) {
        if(pHead == null) return null;
        if(pHead.next == null) return pHead;
        ListNode head = new ListNode(-1);
        head.next = null;
        ListNode prev = head;
        ListNode slow = pHead;
        ListNode fast = pHead.next;
        while(fast != null) {
            if(slow.val != fast.val) {
                prev.next = slow;
                prev = prev.next;
                slow = slow.next;
                fast = fast.next;
            }else {
                while(fast != null && fast.val == slow.val) {
                    fast = fast.next;
                }
                slow = fast;
                if(fast != null) {
                    fast = fast.next;
                }
            }
        }
        prev.next = slow;
        return head.next;
    }
}
